# -*- coding:utf-8
# 5369. 统计作战单位数 显示英文描述
# 用户通过次数163
# 用户尝试次数167
# 通过次数164
# 提交次数171
# 题目难度Medium
#  n 名士兵站成一排。每个士兵都有一个 独一无二 的评分 rating 。
#
# 每 3 个士兵可以组成一个作战单位，分组规则如下：
#
# 从队伍中选出下标分别为 i、j、k 的 3 名士兵，他们的评分分别为 rating[i]、rating[j]、rating[k]
# 作战单位需满足： rating[i] < rating[j] < rating[k] 或者 rating[i] > rating[j] > rating[k] ，其中  0 <= i < j < k < n
# 请你返回按上述条件可以组建的作战单位数量。每个士兵都可以是多个作战单位的一部分。

from typing import List
import math

# 更新dp的同时，更新res；
# dp[i]
# 记录的是第i个数之前比其值小的数的个数；
# 两层判断，如果nums[i] > nums[idx], 更新dp[i]，其次，如果dp[idx] > 0
# 则再更新res。因为此时，num[i]
# 已经大于nums[idx]，再算上一个比nums[idx]
# 小的数，就构成了一个3个数的升序，这样的组合有dp[idx]；
# 另外的一种情况，将数组逆序即可。
# 代码
class Solution:
    def numTeams(self, rating: List[int]) -> int:

        def func(nums):
            dp = [0] * len_
            res = 0
            for i in range(1, len_):
                idx = i - 1
                while idx >= 0:
                    if nums[i] > nums[idx]:
                        dp[i] += 1
                        if dp[idx] > 0:
                            res += dp[idx]
                    idx -= 1
            return res

        len_ = len(rating)
        return func(rating[::-1]) + func(rating)


#想叉了。。。
# class Solution:
#
#     def order(self,n):
#         result = 1
#         for num in range(1, n + 1):
#             result *= num
#         return result
#
#     def combination_number(self,n, m):
#         s1 = self.order(n)
#         s2 = self.order(m)
#         s3 = self.order(n - m)
#         result = s1 / (s2 * s3)
#         return result
#
#     def numTeams(self, rating: List[int]) -> int:
#         sLisCnt ,jLisCnt = 0,0
#         # for num in rating:
#         tongjiDa = [0 for z in range(rating.__len__())]
#         for i in range(rating.__len__()):
#             for j in range(i+1,rating.__len__()):
#                 if rating[j]>rating[i]:
#                     tongjiDa[i]+=1
#         shengxuRes = 0
#         print(tongjiDa)
#         for cnt in tongjiDa:
#             if cnt>2:
#                 shengxuRes+= self.combination_number(cnt,2)
#         print("shengx:",shengxuRes)
#
#         tongjiXiao =  [0 for z in range(rating.__len__())]
#         for i in range(rating.__len__()):
#             for j in range(i+1,rating.__len__()):
#                 if rating[j]<rating[i]:
#                     tongjiXiao[i]+=1
#         jiangxuRes = 0
#         print(tongjiXiao)
#         for cnt in tongjiXiao:
#             if cnt>2:
#                 jiangxuRes+= self.combination_number(cnt,2)
#         print("jiangxu:",jiangxuRes)
#
#         return shengxuRes+jiangxuRes

res = Solution().numTeams(rating = [2,5,3,4,1])
print(res)

